#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

template <typename T>
struct RetType {
    int res;
    T iter;

    RetType(int res, T iter) : res(res), iter(iter) {}
};

class Solution {
public:
    template <typename T>
    RetType<T>* calcForward(T begin, T end);

    template <typename T>
    int calcBackward(T begin, T end);

    template <typename T>
    int waterForward(T begin, T end);

    template <typename T>
    int waterBackward(T begin, T end);

    int trap(vector<int>& height) {
        if (height.size() < 2) {
            return 0;
        }
        auto ret = calcForward(height.begin(), height.end());
        cout << ret->res << ' ' << ret->iter - height.begin() << endl;
        auto res = ret->res;

        if (ret->iter + 1 != height.end()) {
//            cout << "back" << endl;
            res += calcBackward(ret->iter, height.end());
        }
        cout << "result: " << res << endl;
        delete (ret);
        return res;
    }
};

template<typename T>
RetType<T>* Solution::calcForward(T begin, T end) {
    int res = 0;
    auto heightIdx = begin;
    begin++;
    while (begin != end) {
        if (*begin >= *heightIdx) {
            // add new water count
            res += waterForward(heightIdx, begin);
            // update height
            heightIdx = begin;
        }
        begin++;
    }
    return new RetType<typeof(begin)>(res, heightIdx);
}

template<typename T>
int Solution::calcBackward(T begin, T end) {
    int res = 0;
    auto heightIdx = end;
    *end = 0;
    end--;
    while (begin != end) {
        if (*end >= *heightIdx) {
            // add new water count
            res += waterBackward(end, heightIdx);
            // update height
            heightIdx = end;
        }
        end--;
    }
    res += waterBackward(begin, heightIdx);
    cout << res << endl;
    return res;
}

template<typename T>
int Solution::waterForward(T begin, T end) {
    int base = *begin;
    if (begin == end) return 0;
    begin++;
    int res = 0;
    while (begin != end) {
        res += base;
        res -= *begin;
        begin++;
    }
    return res;
}

template<typename T>
int Solution::waterBackward(T begin, T end) {
    int base = *end;
    if (begin == end) return 0;
    end--;
    int res = 0;
    cout << "dis: " << begin - end << endl;
    while (begin != end) {
        cout << res << '\n';
        res += base;
        res -= *end;
        end--;
        cout << "dis: " << begin - end << endl;
    }
    return res;
}


int main() {
    std::cout << "Hello, World!" << std::endl;
    vector<int> vec{5, 5, 1, 7, 1, 1, 5, 2, 7, 6};
    vector<int> vec{0,1,0,2,1,0,1,3,2,1,2,1};
    cout << Solution().trap(vec) << endl;
    return 0;
}
